\documentclass[10pt,a4paper]{article}

\usepackage[utf8]{inputenc}
\usepackage{polski}
\usepackage[polish]{babel}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage[left=2cm,right=2cm,top=2cm,bottom=2cm]{geometry}
\usepackage{algpseudocode}
\usepackage{algorithm}
\usepackage{listings}
\usepackage{color}
 
\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{gray}{rgb}{0.8,0.8,0.8}
\definecolor{mauve}{rgb}{0.58,0,0.82}
 
\lstset{ %
  language=C,                % the language of the code
  basicstyle=\footnotesize,           % the size of the fonts that are used for the code
  numbers=left,                   % where to put the line-numbers
  numberstyle=\tiny\color{gray},  % the style that is used for the line-numbers
  stepnumber=2,                   % the step between two line-numbers. If it's 1, each line 
                                  % will be numbered
  numbersep=5pt,                  % how far the line-numbers are from the code
  backgroundcolor=\color{gray},      % choose the background color. You must add \usepackage{color}
  showspaces=false,               % show spaces adding particular underscores
  showstringspaces=false,         % underline spaces within strings
  showtabs=false,                 % show tabs within strings adding particular underscores
  frame=single,                   % adds a frame around the code
  rulecolor=\color{black},        % if not set, the frame-color may be changed on line-breaks within not-black text (e.g. commens (green here))
  tabsize=2,                      % sets default tabsize to 2 spaces
  captionpos=b,                   % sets the caption-position to bottom
  breaklines=true,                % sets automatic line breaking
  breakatwhitespace=false,        % sets if automatic breaks should only happen at whitespace
  title=\lstname,                   % show the filename of files included with \lstinputlisting;
                                  % also try caption instead of title
  keywordstyle=\color{black},          % keyword style
  commentstyle=\color{dkgreen},       % comment style
  stringstyle=\color{mauve},         % string literal style
  escapeinside={\%*}{*)},            % if you want to add a comment within your code
}







\author{Maciej Donajski}
\title{Algorytm Tabu Search}

\begin{document}
\maketitle

\subsection*{Wstęp}
Algorytm Tabu Search przeszukuje przestrzeń stanów w sposób losowy, ale w odróżnieniu od algorytmu losowego, ułatwia opuszczanie minimów lokalnych w trakcie przeszukiwania. Możliwość tę daje wprowadzenie pamięci krótkoterminowej, w formie listy ruchów zabronionych. Algorytm został zaproponowany przez Freda Glovera w \cite{fg1} i \cite{fg2}.\\

\noindent
Przebieg algorytmu ma następującą postać:


\begin{lstlisting}[caption=Algorytm Tabu Search, label=alg_main]
TabuSearch( inputProblemData ):
	State s    = getInitialState( inputProblemData )
	State best = s

	repeat MAIN_LOOP times:
		Move m = getBestMove( s )
		if not contains( tabuList, m ):
			move( s, m )
			append( tabuList, m )
		
		if isValid( s ) and cost( s ) < cost( best ):
			best = s

	return best
\end{lstlisting}

\noindent
Parametry od których zależy efektywność algorytmu to przede wszystkim rodzaj listy tabu oraz jej rozmiar. Poza tym lepsze efekty można uzyskać przez dokładniejsze przeszukiwanie sąsiedztwa i zwiększenie iteracji głównej pętli algorytmu.

\subsection*{Reprezentacja stanu}
Stan, dla problemu optymalizacji przepływów i lokalizacji zasobów w przeżywalnych systemach obliczeń rozproszonych, reprezentowany jest jako ciąg węzłów. Numer pozycji w ciągu oznacza numer zadania obliczeniowego, a wartość ciągu dla danej pozycji, to indeks węzła wykonującego zadanie. Zatem dla dwóch projektów obliczeniowych, z których każdy ma trzy zadania obliczeniowe i dla trzech węzłów mamy np.:

$$(0, 1, 2, 1, 1, 0),$$

\noindent
co oznacza, że węzeł 0 wykonuje zadania 1 i 6, węzeł 1 wykonuje zadania 2, 4 i 5, a węzeł 2 wykonuje zadanie 3.\\

\noindent
Zadania zabezpieczające są reprezentowane tak samo jak zadania pierwotne, czyli jeśli pierwszy projekt obliczeniowy będzie wymagał zabezpieczenia to stan może mieć postać:

\begin{equation}\label{bad_state}
(0, 1, 2, 1, 1, 0, 1, 2, 2),
\end{equation}

\noindent
trzy ostatnie zadanie są zadaniami zabezpieczającymi dla projektu pierwszego. Warto zauważyć, że zadanie 9 jest wykonywane na tym samym węźle co zadanie 3, stan nie jest więc poprawny. Zadania pierwotne i zabezpieczające nie mogą być wykonywane przez ten sam węzeł.

\subsection*{Reprezentacja ruchu}
Przejście z jednego stanu do stanu sąsiedniego nazywamy ruchem. Ruch definiuje sąsiedztwo i polega na wymianie węzła wykonującego pewne zadanie i wstawienie innego z puli wszystkich węzłów. Operacja reprezentowana jest przez parę liczb, z których pierwsza jest indeksem zadania, a druga indeksem nowego węzła.  Niepoprawny stan (\ref{bad_state}) po wykonaniu ruchu $(9, 1)$ będzie miał postać $(0, 1, 2, 1, 1, 0, 1, 2, 1)$.

\subsection*{Lista Tabu}
Zaproponowane listy tabu przechowują fragmenty ruchów. Zbadano dwa rodzaje listy tabu. Pierwszy zapamiętuje węzeł ostatnio odsunięty od wykonywania jednego z zadań, drugi natomiast zapamiętuje węzeł ostatnio przypisany do wykonywania jednego z zadań. Zgodnie z hipotezą postawioną w \cite{fg3}, lepsze rezultaty otrzymano stosując pierwszy rodzaj listy. \\

\noindent
Z rodzajem listy tabu związane są operacje z linii 7 i 9 listingu \ref{alg_main}.

\subsection*{Generowanie stanu początkowego}
Istotne dla osiągania dobrych wyników jest dobranie stanu wyjściowego. Przeprowadzono badania dla 3 generatorów stanów początkowych:
\begin{itemize}
	\item losowego,
	\item zachłannego -- generator rozpoczyna działanie ze stanu losowego, a następnie iterując się po wszystkich zadaniach i zamienia obecnie przyporządkowane węzły na takie które najbardziej zmniejszają koszt stanu,
	\item heurystycznego -- generator iteruje się po wszystkich zadaniach i przyporządkowuje w pierwszej kolejności węzły docelowe danego zadania, następnie węzeł źródłowy zadania, a jeśli to nie jest możliwe to postępuje tak samo jak generator zachłanny. W ten sposób unikamy przesyłania i pobierania wyników lub danych wejściowych obliczeń do wybranego węzła.	
\end{itemize}

\noindent
Najlepsze rezultaty otrzymano dla generatora heurystycznego.

\subsubsection*{Optymalizacja} 
Istotne przyspieszenie działania algorytmu można uzyskać jeśli podczas przeszukiwania sąsiedztwa rozważamy różnicę pomiędzy stanem przed ruchem i po przeprowadzeniu ruchu. Wówczas nie trzeba iterować się po wszystkich węzłach i wszystkich zadaniach, żeby obliczyć koszt stanu po przeprowadzeniu ruchu. Zauważmy, że ruch wprowadza zmiany na maksymalnie 3 węzłach -- węźle źródłowym zadania, węźle wykonującym obecnie zadanie i węźle, który będzie wykonywał zadanie po przeprowadzeniu ruchu. Uwzględniając ten fakt, złożoność obliczania kosztu po ruchu wynosi $O(1)$.


\subsection*{Funkcja kary}
W trakcie przeszukiwania sąsiedztwa, dopuszczane są węzły nie spełniające ograniczeń problemu. Eksperymenty wykazały, że węzły nieprawidłowe należy  dopuszczać warunknowo. Okazało się, że algorytm akceptując rozwiązanie nieprawidłowe, które zwykle ma mniejszy koszt, nie powraca do przestrzeni rozwiązań prawidłowych. Zastosowano zatem funkcję kary. Stan nieprawidłowy $newState$ jest akceptowany jeśli spełnia nierówność

$$ cost( oldState ) > cost( newState ) + penalty( newState ),$$

\noindent
gdzie funkcja $penalty$ jest funkcją kary. Zaimplementowano funkcję kary, która przyjmuje większe wartości dla stanów, które w większym stopniu przekraczają ograniczenie maksymalenej wydajności węzła obliczeniowego. Funkcja kary ma następującą postać

$$penalty( state ) = P \cdot cost( state ) \cdot \frac{\sum_n max(0, currentProcessing[n] - maximumProcessing[n])}{\sum_n maximumProcessing[n]},$$

\noindent
gdzie $currentProcessing[n]$ to liczba obecnie wykonywanych zadań przez węzeł $n$, a $maximumProcessing[n]$ to maksymalna liczba zadań, które może wykonywać węzeł $n$. Dodatkowo wprowadzono parametr $P$, zadawany przed wykonywaniem algorytmu.

\subsection*{Dobór parametrów algorytmu}
Excel w załączniku

\end{document}